#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

// 定义内核风格的双向循环链表头
struct list_head {
    struct list_head *next, *prev;
};

// 初始化链表头宏
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

// 初始化链表节点
static inline void INIT_LIST_HEAD(struct list_head *head) {
    head->next = head;
    head->prev = head;
}

// 向链表尾部添加节点（队列尾部入队）
static inline void list_add_tail(struct list_head *new_node, struct list_head *head) {
    new_node->prev = head->prev;
    new_node->next = head;
    head->prev->next = new_node;
    head->prev = new_node;
}

// 从链表中删除节点
static inline void list_del(struct list_head *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 容器_of宏：通过链表节点获取结构体指针
//#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__m = (ptr); \
    (type *)( (char *)__m - offsetof(type, member) ); \
})

// 队列元素结构体（包含数据和链表节点）
struct queue_node {
    int data;          // 数据域
    struct list_head list; // 链表节点
};

// 队列结构体（包含链表头和大小）
struct queue {
    struct list_head head; // 链表头（虚拟节点，不存储数据）
    int size;              // 队列大小
};

// 初始化队列
void queue_init(struct queue *q) {
    INIT_LIST_HEAD(&q->head); // 初始化双向循环链表
    q->size = 0;
}

// 判断队列是否为空
int queue_is_empty(struct queue *q) {
    return (q->head.next == &q->head); // 头节点的next指向自身表示空
}

// 入队操作（从队列尾部添加元素）
void queue_enqueue(struct queue *q, int data) {
    struct queue_node *new_node = malloc(sizeof(struct queue_node));
    if (!new_node) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    new_node->data = data;
    list_add_tail(&new_node->list, &q->head); // 插入到链表尾部
    q->size++;
}

// 出队操作（从队列头部删除元素并返回数据）
int queue_dequeue(struct queue *q) {
    if (queue_is_empty(q)) {
        fprintf(stderr, "Error: queue is empty\n");
        exit(EXIT_FAILURE);
    }
    struct list_head *front = q->head.next; // 队首节点（头节点的下一个节点）
    struct queue_node *node = container_of(front, struct queue_node, list);
    int data = node->data;
    
    list_del(front); // 删除节点
    free(node);
    q->size--;
    return data;
}

// 查看队首元素（不删除）
int queue_peek(struct queue *q) {
    if (queue_is_empty(q)) {
        fprintf(stderr, "Error: queue is empty\n");
        exit(EXIT_FAILURE);
    }
    struct list_head *front = q->head.next;
    struct queue_node *node = container_of(front, struct queue_node, list);
    return node->data;
}

// 获取队列大小
int queue_size(struct queue *q) {
    return q->size;
}

// 示例用法
int main() {
    struct queue q;
    queue_init(&q);

    // 入队操作
    queue_enqueue(&q, 10);
    queue_enqueue(&q, 20);
    queue_enqueue(&q, 30);
    printf("Queue size: %d\n", queue_size(&q)); // 输出：3
    printf("Front element: %d\n", queue_peek(&q)); // 输出：10

    // 出队操作
    printf("Dequeue: %d\n", queue_dequeue(&q)); // 输出：10
    printf("Dequeue: %d\n", queue_dequeue(&q)); // 输出：10
    printf("Dequeue: %d\n", queue_dequeue(&q)); // 输出：10
    printf("New front: %d\n", queue_peek(&q)); // 输出：20
    printf("Queue size: %d\n", queue_size(&q)); // 输出：2

    return 0;
}
